\section{Exact WCRT for a self-suspending task with one self-suspending region}
\label{sec:oneself}

In this section, we restrict our analysis to the special case of a self-suspending task $\sstask$ composed of only two execution regions and one suspension region. We propose an algorithm to compute the exact worst-case response time of such a task. Self-suspending tasks with multiple suspension regions will be considered in the next section. 

%As proven in Lemma~\ref{lem:proof1}, the critical instant for $\sstask$ happens when all the higher priority tasks release a job synchronously with the first and/or the second execution region of the self-suspending task. 
As proven in Lemma~\ref{lem:proof1}, the critical instant for $\sstask$ happens when a job of every higher priority task is released synchronously with the release of the first and/or second execution region of $\sstask$.
However, since we do not know a priori which combination of synchronous releases corresponds to the critical instant, there is no other solution for an exact WCRT analysis than considering all the possible combinations of synchronous releases. The exact WCRT for $\sstask$ is thus given by the maximum response time obtained with any of these combinations. 
Consequently, the WCRT analysis problem boils down to the subproblem of computing the WCRT of $\sstask$ when the higher priority tasks in $\hp{ss}$ are constrained to have a synchronous release with a specific execution region of $\sstask$. We will later refer to that subproblem as the \emph{``constrained releases subproblem''}.

%Alg.~\ref{alg:resp_time_one_selfsusp} provides the pseudo-code of the worst-case response time analysis for a self-suspending $\sstask$ with one self-suspending region. The function ``RespTime'' called at line~\ref{ln:RespTime_call} computes the WCRT for the constrained releases subproblem and takes as arguments the set of higher priority tasks and a subset $\synch{2}$ of those tasks that are constrained to have a synchronous release with the second execution region of $\sstask$.
%
%
%
%\newcommand{\TaskCombInst}[1]{\operatorname{TaskComb}_{#1}}
%\newcommand{\TaskComb}[1]{\operatorname{TaskComb}(#1)}
%
%\begin{algorithm}[h]
%\small
%
%\KwData{$\TaskComb{\hp{ss}}$ - a set of all possible combinations of the tasks in $\hp{ss}$}
%
%$R_{ss} \leftarrow 0$\;
%\ForAll{combinations $\TaskCombInst{k} \in \TaskComb{\hp{ss}}$}
%{
%    $\synch{2} \leftarrow \TaskCombInst{k}$\;
%    $R \leftarrow$~ RespTime($\hp{ss}$,~$\synch{2}$) \label{ln:RespTime_call} \;
%    \If{$R > R_{ss}$}
%    {
%        $R_{ss} \leftarrow R$\;
%    }
%}
%
%\caption{Computation of the WCRT of a self-suspending task with one self-suspending region.}
%\label{alg:resp_time_one_selfsusp}
%\end{algorithm}

\subsection{Discussion on the constrained releases subproblem}
\label{sec:oneself_nontrivial}

\newcommand{\NI}[1]{\operatorname{NI}_{#1}}
\newcommand{\NImax}[1]{\operatorname{NI_{#1}^{\max}}}

Let us consider a self-suspending task $\sstask$, a set of higher priority tasks $\hp{ss}$ and a subset $\synch{2}$ of $\hp{ss}$ containing tasks constrained to have a synchronous release with the second execution region of $\sstask$. The WCRT of the first execution region $\ssregion{1}$ of $\sstask$ under those circumstances can be computed as follows
\begin{equation}
R_{ss,1} = C_{ss,1} + \sum_{\forall k\in \hp{ss}} \NI{k} \times C_k
\label{eq:resp_ss1}
\end{equation}
where $\NI{k}$ is the maximum number of jobs of $\tau_k$ interfering with $\sstask$. According to the usual response time analysis for sporadic tasks with fixed priorities, $\NI{k}$ is subject to the following constraint 
\begin{align}
\NI{k} \leq \left\lceil \frac{R_{ss,1}}{T_k} \right\rceil
\label{eq:usual_ceil}
\end{align}
Furthermore, for the higher priority tasks that are constrained to have a synchronous release with $\ssregion{2}$, one must ensure that
\begin{align}
\forall \tau_k \in \synch{2}, ~ \NI{k} \times T_k \leq R_{ss,1} + S_{ss,1}
\label{eq:constr_NI_2}
\end{align}
in order to respect the minimum inter-arrival time $T_k$ of $\tau_k$. That is, for every higher priority task $\tau_k$ that has a synchronous release with $\ssregion{2}$, the release of its last job interfering with $\ssregion{1}$, happening at time $(\NI{k}-1)\times T_k$, and the beginning of $\ssregion{2}$ at time $R_{ss,1} + S_{ss,1}$, have to be separated by at least $T_k$ time units.

As a consequence of those constraints, the following equation can be used for $\NI{k}$ and substituted in Eq.~\eqref{eq:resp_ss1}
\begin{equation}
\NI{k} = \begin{cases}
         \min\left(\left\lceil \frac{R_{ss,1}}{T_k} \right\rceil, \left\lfloor \frac{R_{ss,1} + S_{ss,1}}{T_k} \right\rfloor \right) & \text{if $\tau_k \in \synch{2}$} \\
         \left\lceil \frac{R_{ss,1}}{T_k} \right\rceil & \text{otherwise}
 \end{cases}
\label{eq:NI}
\end{equation}

When combined with Eq.~\eqref{eq:NI}, Eq.~\eqref{eq:resp_ss1} becomes recursive. This kind of equation is usually solved using a fixed point iteration on $R_{ss,1}$. However, as shown in the example below, contrary to the traditional WCRT analysis of non-self-suspending sporadic tasks, the first solution found to this equation by increasing the value of $R_{ss,1}$ until it converges may yield to an optimistic (and unsafe) value. 

\begin{Example}
\label{ex:forward_iteration}
Consider a self-suspending task $\sstask$ such that $C_{ss,1}=3$ and $S_{ss,1}=1$, and two higher priority tasks $\tau_1 \equals \left\langle(1),5,5\right\rangle$ and $\tau_2 \equals \left\langle(2),6,6\right\rangle$. Let us assume that both $\tau_1$ and $\tau_2$ are constrained to have a synchronous release with $\ssregion{2}$. It can be verified that the WCRT of $\ssregion{1}$ under those constraints is given when both $\tau_1$ and $\tau_2$ release one job in $\ssregion{1}$, that is, $R_{ss,1} = 6$. However, using a fixed point iteration with Eq.~\eqref{eq:resp_ss1} and~\eqref{eq:NI}, initiating $R_{ss,1}$ to $C_{ss,1}=3$, the process immediately converges to $R_{ss,1} = 3$, thereby assuming no job released by the higher priority tasks.\qed
\end{Example}

This example shows that the usual fixed-point iteration approach, initiating $R_{ss,1}$ with $C_{ss,1}$, is unsafe. Yet, solving Eq.~\eqref{eq:resp_ss1} with $\NI{k} = \left\lceil \frac{R_{ss,1}}{T_k} \right\rceil$ for all tasks in $\hp{ss}$ --- that is, when there is no constraint on the task releases --- is known to be an upper-bound on the WCRT of $\ssregion{1}$ \cite{Tindell:MM1994}. Let $\UB{1}$ be the value of that upper-bound. Based on the observation that increasing $R_{ss,1}$ until its convergence might be optimistic, one might propose to start the fixed point iteration on $R_{ss,1}$ by initiating $R_{ss,1}$ to $\UB{1}$. Then, the value of $R_{ss,1}$ should decrease over the iterations thanks to the constraint $\NI{k} \leq \left\lfloor \frac{R_{ss,1} + S_{ss,1}}{T_k} \right\rfloor$. However, as proven in the example provided below, the new solution output by this second method can over-estimate the WCRT of $\ssregion{1}$.

\begin{Example}
Consider the same set of tasks as in Example~\ref{ex:forward_iteration}, but let us assume that $\tau_1$ must have a synchronous release with $\ssregion{2}$ and $\tau_2$ with $\ssregion{1}$. It can be computed that the WCRT of $\ssregion{1}$ under those constraints is given when both $\tau_1$ and $\tau_2$ release one job in $\ssregion{1}$, that is, $R_{ss,1} = 6$. Moreover, the WCRT of $\ssregion{1}$ is known to be upper-bounded by $\UB{1}= 9$. %(this can be obtained by solving Eq.~\eqref{eq:resp_ss1} assuming no constraints on the synchronous releases).
If we initiate the fixed point iteration on $R_{ss,1}$ in Eq.~\eqref{eq:resp_ss1} with $\UB{1}$, we obtain $R_{ss,1} = 8$. This is impossible since it would mean that $\tau_2$ releases two jobs in $\ssregion{1}$, that is ,its second job would be released at time $6$ when $\ssregion{1}$ just completed its execution. \qed
\end{Example}

These two examples show that, in the general case, no simple method exists yet to find a exact solution to the constrained releases subproblem.

\subsection{Solution for the constrained releases subproblem}

In this section, we propose a method to compute the exact WCRT on the sum of $R_{ss,1}$ and $R_{ss,2}$ under a set of release constraints $\synch{2}$. 

The proposed method to compute $R_{ss,1}$ is based on a combination of the two straightforward but inexact solutions investigated in Section~\ref{sec:oneself_nontrivial}. That is, we simultaneously increase and decrease the value of $R_{ss,1}$ in two different but interdependent iterative processes until they converge to the same value. To do so, Eq.~\eqref{eq:NI} is rewritten as follows
\begin{align}
\NI{k} = \begin{cases}
         \min\left(\left\lceil \frac{R_{ss,1}}{T_k} \right\rceil, \NImax{k} \right) & \text{if $\tau_k \in \synch{2}$} \\
         \left\lceil \frac{R_{ss,1}}{T_k} \right\rceil & \text{otherwise}
 \end{cases}
\label{eq:NI_new}
\end{align}
where $\NImax{k}$ is an upper-bound on the number of jobs of $\tau_k$ interfering with the first execution region of $\sstask$. This new formulation of Eq.~\ref{eq:NI} removes the recursiveness in the term enforcing compliance with the constraints imposed by $\synch{2}$. The WCRT can therefore be computed with the usual fixed-point iteration on $R_{ss,1}$ where $R_{ss,1}$ is initialized to $C_{ss,1}$ for the first iteration. During that process, $\NImax{k}$ is assigned a known upper-bound on $\NI{k}$. Because $\NImax{k}$ is an upper-bound, the result obtained for $R_{ss,1}$ after convergence of Eq.~\eqref{eq:NI_new} is also an upper-bound on the actual WCRT of $\ssregion{1}$. However, with this value, the constraint expressed by Eq.~\eqref{eq:constr_NI_2} may not be respected. Therefore, the constraint imposed by Eq.~\eqref{eq:constr_NI_2} is checked. If violated, the value of $\NImax{k}$ is decreased and Eq.~\eqref{eq:resp_ss1} is solved again. Otherwise, an exact WCRT for $\ssregion{1}$ has been found. 

Lines~\ref{ln:firstline} to~\ref{ln:endconvergence} of Algorithm~\ref{algo:rt1} present a pseudo-code of that method. Starting with the upper bound $\UB{1}$ on $R_{ss,1}$ (line~\ref{ln:upperbound}), it iteratively removes jobs of higher priority tasks interfering with $\ssregion{1}$ (lines~\ref{ln:begining_jobupdate}--\ref{ln:end_jobupdate}) when the condition expressed in Eq.~\eqref{eq:constr_NI_2} is violated, i.e., $\NI{k} > \frac{R_{ss,1} + S_{ss,1}}{T_k}$. With this updated value, the response time $R_{ss,1}$ is recomputed at line~\ref{ln:Rss1} of Algorithm~\ref{algo:rt1}. This process iterates until the value computed for $R_{ss,1}$ converges to the exact WCRT of $\ssregion{1}$ under the constraints imposed by $\synch{2}$.

\newcommand{\Rback}{R_{ss,1}^{\operatorname{bwd}}}
\newcommand{\Rfor}{R_{ss,1}^{\operatorname{fwd}}}
\newcommand{\Offset}[1]{O_{#1,2}}

\begin{algorithm}[t!]
\small

\SetKwProg{Fn}{Function}{ is}{end}

\Fn{RespTime ( $\hp{ss}$,~$\synch{2}$,~$NI^{\operatorname{up}}$ )}{

\SetKwInOut{Input}{Inputs}\SetKwInOut{Output}{Output}
   \Input{$\hp{ss}$ - set of higher priority tasks w.r.t. $\sstask$\\
        $\synch{2}$ - the set of tasks in $\hp{ss}$ with an imposed synchronous release with $\ssregion{2}$\\
        $NI^{\operatorname{up}}$ - vector of upper bounds on the number of jobs of each task $\tau_k$, that can interfere with $\ssregion{1}$}
   \Output{$R_{ss}$ - The exact WCRT for $\sstask$ when respecting the constraints given by $\synch{2}$ and $NI^{\operatorname{up}}$}
   
   \BlankLine
   
	 $\Rback \leftarrow 0$ \label{ln:firstline}\;
	 $NI \leftarrow NI^{\operatorname{up}}$\;
	 $R_{ss,1} \leftarrow C_{ss,1} + \sum\limits_{\forall k\in \hp{ss}} NI^{\operatorname{up}}_k \times C_k$ \label{ln:upperbound}\;
	 
	 
	 \While{$\Rback \neq R_{ss,1}$} {
	 
	     \BlankLine
	     $\Rback \leftarrow R_{ss,1}$ \;
		
	     \tcc{Update the number of interfering jobs for the tasks synchronous with $\ssregion{2}$} 
		\ForAll{$\tau_k \in \synch{2}$} 
	     { \label{ln:begining_jobupdate}
		    \If{$NI_k > \frac{R_{ss,1} + S_{ss,1}}{T_k}$} {
			    $NI_k \leftarrow NI_k - 1$ \;
		    }
		 } \label{ln:end_jobupdate}
		 

%		\tcc{Compute the response time of $\ssregion{1}$ with a fixed point iteration}
%		$\Rfor \leftarrow 0$\;
%		$R_{i,1} \leftarrow C_{ss,1}$\;
%		 \While{$\Rfor \neq R_{ss,1}$} {
%			$\Rfor \leftarrow R_{ss,1}$\;
%			$R_{ss,1} \leftarrow C_{ss,1} + \sum\limits_{\forall k\in \hp{ss}} \min(NI_k; \left\lceil \frac{\Rfor}{T_k} \right\rceil) \times C_k$\;
%		}
		
		\tcp{Compute the response time of $\ssregion{1}$}
		$R_{ss,1} \leftarrow C_{ss,1} + \sum\limits_{\forall k\in \hp{ss}} \min(NI_k; \left\lceil \frac{R_{ss,1}}{T_k} \right\rceil) \times C_k$\; \label{ln:Rss1}
		
%		\ForAll{$\tau_k \in \hp{ss}$}
%	     {
%	         $NI_k \leftarrow \left\lceil \frac{R_{ss,1}}{T_k} \right\rceil$ \;
%	     }
	     
	     \textbf{forall the} $\tau_k \in \hp{ss}$ \textbf{do} $NI_k \leftarrow \left\lceil \frac{R_{ss,1}}{T_k} \right\rceil$\;
	 } \label{ln:endconvergence}
	 
	 \tcp{Compute the offsets with $\ssregion{2}$}	 
	 \ForAll{$\tau_k \in \hp{ss}$}
	 { \label{ln:begining_resp2}
	     $\Offset{k} \leftarrow \max(0; NI_k \times T_k - R_{ss,1} - S_{ss,1})$\;
	 }
	 
	 \tcp{Compute the response time of $\ssregion{2}$}
	 $R_{ss,2} \leftarrow C_{ss,2} + \sum\limits_{\forall k\in \hp{ss}} \left\lceil \frac{R_{ss,2} - \Offset{k}}{T_k} \right\rceil \times C_k$\; \label{ln:end_resp2}
	 
	 $R_{ss} \leftarrow R_{ss,1} + S_{ss,1} + R_{ss,2};$ \; \label{ln:overall_resp}
	 
	 \BlankLine
	 
	 \tcc{Check if there is not a release pattern with one less job in $\ssregion{1}$ that increases the overall WCRT}
	 \If{$R_{ss} < \operatorname{UB}_{ss}$ and $R_{ss,2} < \UB{2}$}
	 { \label{ln:beginning_recursion}
	     \ForAll{$\tau_k \in \hp{ss}$}
	     {
	         \If{$NI_k > 0$}
	         {
	         $NI' \leftarrow NI$ \;
	         
	         $NI'_k \leftarrow NI_k - 1$ \;
	         $R \leftarrow $~RespTime($\hp{ss}$,~$\synch{2}$,~$NI'$)\;
	         \textbf{If} $R > R_{ss}$ \textbf{then} $R_{ss} \leftarrow R$\;
	         }
	     }
	 }	 \label{ln:end_recursion}
	 	 
	 \Return $R_{ss}$\;
}
\caption{Computation of the WCRT of $\sstask$ assuming a set of constraints on higher priority tasks releases}
\label{algo:rt1}
\end{algorithm}


%Following the traditional response time equation (with no offsets), response time's convergence cannot be attained by a lower number of interfering jobs. Otherwise the number of interfering jobs for each higher priority tasks is given by the new value of response time.

Once the response time of $\ssregion{1}$ has been computed, the offset $\Offset{k}$ can be obtained with Eq.~\eqref{eq:offset_ss2}. This offset accounts for the difference between the earliest instant at which each task $\tau_k$ can release a job in $\ssregion{2}$, while respecting its minimum inter-arrival time $T_k$, and the beginning of $\ssregion{2}$.
%Once the response time of $\ssregion{1}$ has been computed, the offset $\Offset{k}$ that accounts for the difference between the beginning of $\ssregion{2}$ and the earliest instant at which each task $\tau_k$ can release a job in $\ssregion{2}$ while respecting its minimum inter-arrival time $T_k$ can be obtained with Eq.~\eqref{eq:offset_ss2}.
\begin{equation}
\resizebox{0.91\columnwidth}{!}{$
\Offset{k} =  
  \begin{cases}
    0 & \text{if $\tau_k \in \synch{2}$}\\
    \max\{0, ~\NI{k} \times T_k - (R_{ss,1} + S_{ss,1})\} & \text{otherwise}
  \end{cases}
$}
\label{eq:offset_ss2}
\end{equation}
As expressed by Eq.~\eqref{eq:offset_ss2}, any release of a job of $\tau_k$ that should happen within the suspension region of $\sstask$ is delayed until the beginning of $\ssregion{2}$, thereby imposing $\Offset{k} = 0$. This allows us to maximize the interference caused by $\tau_k$ to $\ssregion{2}$.

$R_{ss,2}$ is given by Eq.~\eqref{eq:resp_ss2} and is computed as the traditional response time for non-self-suspending tasks. That is, we seek a minimum response time that satisfies the fixed-point iteration by starting with $R_{ss,2}= C_{ss,2}$. In Algorithm~\ref{algo:rt1}, this is reflected in lines~\ref{ln:begining_resp2} to~\ref{ln:end_resp2}. 
\begin{equation}
R_{ss,2} = C_{ss,2} + \sum_{\forall k\in hp(\tau_i)} \ceil[\bigg]{\frac{R_{ss,2} - O_{k,2}}{T_k}} \times C_k
\label{eq:resp_ss2}
\end{equation}

%The offset for higher priority tasks that do not have a synchronous release with $C_{ss,2}$ (i.e. they have a synchronous release exclusively with $C_{ss,1}$) depends on the response time of the first computing segment of $\tau_i$. Therefore we must find $R_{ss,1}$ first.

Line~\ref{ln:overall_resp} computes the overall response time of $\sstask$. However, as proven in Section~\ref{sec:example2}, it might happen that releasing one less job in $\ssregion{1}$ allows to increase the response time of $\ssregion{2}$ and in turn increase the overall response time of $\sstask$. Therefore, lines~\ref{ln:beginning_recursion} to \ref{ln:end_recursion} have been added to consider that case. Those lines call recursively the function RespTime, imposing the upper-bound on the number of interfering jobs with the first execution region to be one less than in the computed solution. Of course, this recursion must not be activated if the overall response time $R_{ss}$ found for $\sstask$ is already equal to a known upper-bound obtained with simple approximation techniques likes those proposed in \cite{btesas:thesis2007}. Similarly, there is no need trying to increase the response time of $\ssregion{2}$ by reducing the response time of $\ssregion{1}$ if $R_{ss,2}$ is already equal to an upper-bound.

It can easily be seen by looking at Algorithm~\ref{algo:rt1}, that computing the exact WCRT of $\sstask$ becomes rapidly intractable. This fact has been confirmed by the experiments reported in Section~\ref{sec:experiments}. Therefore, in the next section, we propose a second method, using a MILP formulation, to compute an approximation over the WCRT of $\sstask$.

%Unfortunately, computing $R_{i,1}$ is not trivial as it must be computed backward when at least one task has a synchronous release with $C_{i,2}$. Due to this peculiarity, following the same strategy of increasing the response time until it converges may yield an optimistic value for $R_{i,1}$. Based on this observation, we compute $R_{i,1}$ by decreasing its maximum value. 



%Accordingly, the exact response time for $R_{i,1}$ can then be computed by the procedure shown in Algorithm~\ref{algo:rt1}. Condition 1) is satisfied in lines~5-7, whereas condition 2) is enforced in lines~11-15. A release pattern $X$ is a binary array of $n-1$ elements, where each element is set to 1 if the corresponding higher priority task is assumed to have a synchronous release with the last computing segment of $\tau_i$. Let $NI_k$  denote the number of interfering jobs of task $\tau_k$

